package com.study.tree;

import java.util.Stack;

/**
 * - *@ClassName TreeTest
 * - *@Author LiuHuaBing
 * - *@Date 2021/12/16 15:25
 * - *@Version 1.0
 * <p>递归序 遍历二叉树 可以由递归序变化出前序中序后序遍历结果</>
 */
public class TreeTest {
    public static void main(String[] args) {
        Tree tree = createTree();

        //preUnrecursionErgodic(tree.getRoot());
        //posUnrecursionErgodic(tree.getRoot());
        midUnrecursionErgodic(tree.getRoot());
        //recursionErgodic(tree);

    }

    public static Tree createTree() {
        Tree<Integer> tree = new Tree<>(new TreeNode<>(0));

        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode7 = new TreeNode(7);
        TreeNode treeNode8 = new TreeNode(8);

        tree.getRoot().left = treeNode1;
        tree.getRoot().right = treeNode2;
        tree.getRoot().left.left = treeNode3;
        tree.getRoot().left.right = treeNode4;
        tree.getRoot().right.left = treeNode5;
        tree.getRoot().right.right = treeNode6;
        tree.getRoot().left.left.left = treeNode7;
        tree.getRoot().left.left.right = treeNode8;

        return tree;
    }

    // recursionErgodic
    private static void recursionErgodic(Tree tree) {
        function(tree.getRoot());

    }

    private static void function(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        System.out.println(treeNode.value);
        function(treeNode.left);
        function(treeNode.right);
    }

    // unrecursionErgodic front order
    private static void preUnrecursionErgodic(TreeNode head) {

        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);
        while (!stack.empty()) {
            head = stack.pop();
            System.out.println(head.value);
            if (head.right != null) {
                stack.push(head.right);
            }
            if (head.left != null) {
                stack.push(head.left);
            }
        }
    }

    // unrecursionErgodic Middle order
    private static void midUnrecursionErgodic(TreeNode head) {
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.empty() || head !=null){
            if (head!=null){
                stack.push(head);
                head = head.left;
            }else {
                head = stack.pop();
                System.out.println(head.value);
                if (head.right!=null);
                head =head.right;
            }


        }



    }

    // unrecursionErgodic Post order
    private static void posUnrecursionErgodic(TreeNode head) {
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(head);
        while (!stack1.empty()){
            head = stack1.pop();
            stack2.push(head);
            if (head.left!=null){
                stack1.push(head.left);
            }
            if (head.right!=null){
                stack1.push(head.right);
            }
        }
        while (!stack2.empty()){
            System.out.println(stack2.pop().value);
        }
    }


}
